package com.lw.leetcode.stack.c;

import java.util.Stack;

/**
 * 85. 最大矩形
 *
 * @Author liw
 * @Date 2021/6/16 20:23
 * @Version 1.0
 */
public class MaximalRectangle {

    private Stack<Integer> index = new Stack<>();
    private Stack<Integer> value = new Stack<>();

    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int b = matrix[0].length;
        if (b == 0) {
            return 0;
        }
        int m = 0;
        index.add(-1);
        value.add(0);

        int[] arr = new int[b];
        for (char[] chars : matrix) {
            for (int i = 0; i < b; i++) {
                if (chars[i] == '0') {
                    arr[i] = 0;
                } else {
                    arr[i] += 1;
                }
            }
            m = Math.max(m, largestRectangleArea(arr));
        }
        return m;
    }

    private int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int length = heights.length;
        int max = 0;
        for (int i = 0; i < length; i++) {
            int v = heights[i];
            if (value.peek() > v) {
                Integer st = index.peek();
                while (value.peek() > v) {
                    int item = value.pop();
                    index.pop();
                    int l = st - index.peek();
                    max = Math.max(max, l * item);
                }
            }
            value.add(v);
            index.add(i);
        }
        if (!value.isEmpty()) {
            Integer st = index.peek();
            while (value.size() > 1) {
                int item = value.pop();
                index.pop();
                int l = st - index.peek();
                max = Math.max(max, l * item);
            }
        }
        return max;
    }
}
